Xét đồ thị G sau:

• Cho tập W={3,4,5,6}. Đồ thị R sinh bởi W có tập đỉnh {3,4,5,6} và tập cạnh là {(3,4),(3,5),(4,5),(4,6),(5,6)}. Dễ dàng thấy được cây khung nhỏ nhất của R có các cạnh {(3,4),(4,6),(6,5)} với tổng trọng số là 13. Tuy nhiên với tập đỉnh {3,4,5,6,1} có cây khung là {(3,4),(4,1),(1,6),(6,5)} chỉ có tồng trọng số là 12 < 13. Ở đây 1 được gọi là điểm Steiner.
• Bây giờ ta sẽ xây dựng phương pháp giải bài toán Steiner bằng cách sử dụng thuật toán Floyd-Warshall tìm khoảng cách và đường đi ngắn nhất và thuật toán Kruskal để tìm cây khung nhỏ nhất.

Các bước thực hiện

• Đầu vào: Trọng đồ thị liên thông G=(V,E,w) gồm n đỉnh và tập W ⊂ V m đỉnh, m < n.
• Đầu ra: Cây Steiner của W trong G.
• Các bước:
  • Bước 1: Xây dựng đồ đơn đủ có trọng số G’=(V,F,w’) (bằng thuật toán Floyd-Warshall), trong đó w’(u,v) là khoảng cách ngắn nhất từ u đến v với mọi cặp (u,v).
  • Bước 2: Với mỗi S ⊂ V-W, card(S) ≤ m-2, tìm cây khung nhỏ nhất của đồ thị <W∪S> sinh bởi W∪S trong G’. Trong các cây khung đó tìm cây T’ có trọng số nhỏ nhất (dùng thuật toán Kruskal hoặc Prim).
  • Bước 3: Xây dựng cây Steiner T từ T’ bằng cách thay mỗi cạnh nối hai đỉnh trong G’ bằng đường đi nối chúng với nhau trong G. Các đỉnh thuộc T mà không thuộc W là những đỉnh Steiner.